package leetcode_900;

/**
 *@author 周杨
 *SoupServings_808 给四种汤服务 问最终的一个概率
 *describe:题目没有看太明白 用递归 AC 73%
 *see:https://blog.csdn.net/laputafallen/article/details/79777115
 *2018年10月26日 上午9:59:47
 */
public class SoupServings_808 {
	double[][] memo = new double[200][200];
    public double soupServings(int N) {
        return N >= 4800 ?  1.0 : f((N + 24) / 25, (N + 24) / 25);
    }

    public double f(int a, int b) {
        if (a <= 0 && b <= 0) return 0.5;
        if (a <= 0) return 1;
        if (b <= 0) return 0;
        if (memo[a][b] > 0) return memo[a][b];
        memo[a][b] = 0.25 * (f(a - 4, b) + f(a - 3, b - 1) + f(a - 2, b - 2) + f(a - 1, b - 3));
        return memo[a][b];
    }
}
